package main

import "fmt"

type Stack struct {
	ByteList []byte
}

func (s *Stack) Push(b byte) {
	s.ByteList = append(s.ByteList, b)
}

func (s *Stack) Pop() byte {
	if s.IsNull() {
		return 0
	}
	b := s.ByteList[len(s.ByteList)-1]
	s.ByteList = s.ByteList[:len(s.ByteList)-1]
	return b
}

func (s *Stack) IsNull() bool {
	return len(s.ByteList) == 0
}

func isValid(s string) bool {
	n := len(s)
	if n%2 == 1 {
		return false
	}
	pairs := map[byte]byte{
		'}': '{',
		']': '[',
		')': '(',
	}
	stack := Stack{}
	for i := 0; i < n; i++ {
		if pairs[s[i]] > 0 {
			if stack.IsNull() || stack.Pop() != pairs[s[i]] {
				return false
			}
		} else {
			stack.Push(s[i])
		}
	}
	return stack.IsNull()
}

func main() {
	fmt.Println(isValid("()"))
	fmt.Println(isValid("()[]{}"))
}
